#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        ListNode *dummy = new ListNode(0);
        ListNode *pre;
        while (head != NULL && head->next != NULL)
        {
            if (head->val <= head->next->val)
            {
                head = head->next;
                continue;
            }
            pre = dummy;
            while (pre->next->val < head->next->val)
            {
                pre = pre->next;
            }
            ListNode *cur = head->next;
            head->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
        }
        ListNode *res = dummy->next;
        delete dummy;
        return res;
    }
};